package com.lun.medium;

import java.util.ArrayList;
import java.util.List;

public class RestoreIPAddresses {

	public List<String> restoreIpAddresses(String s) {
		List<String> result = new ArrayList<>();
		backtracking(new StringBuilder(), s, 0, 0, result);
		return result;
	}

	private void backtracking(StringBuilder sb, String originalString, //
			int startIndex, int dotNum, List<String> result) {

		if (dotNum == 3) {
			if (isValid(originalString, startIndex, originalString.length())) {
				result.add(sb.toString() + originalString.substring(startIndex, originalString.length()));
			}
			return;
		}

		// i为变化的endIndex，横向
		for (int i = startIndex + 1; i <= originalString.length(); i++) {
			if (!isValid(originalString, startIndex, i))
				break;

			sb.append(originalString.substring(startIndex, i));
			sb.append('.');
			backtracking(sb, originalString, i, dotNum + 1, result);
			sb.delete(sb.length() - (i - startIndex) - 1, sb.length());// 回溯
		}

	}

	private boolean isValid(String str, int startIndex, int endIndex) {

		int diff = endIndex - startIndex;

		if (diff <= 0 || diff >= 4) {
			return false;
		}

		if (diff == 2) {
			if (str.charAt(startIndex) == '0')
				return false;
		}

		if (diff == 3) {
			if (str.charAt(startIndex) == '0' || // 针对IPv4第4个数可能是"012"
					str.charAt(startIndex) > '2') {// 3XX
				return false;
			}

			if (str.charAt(startIndex) == '2' && //
					str.charAt(startIndex + 1) > '5') {// 26X
				return false;
			}

			if (str.charAt(startIndex) == '2' && //
					str.charAt(startIndex + 1) == '5' && //
					str.charAt(startIndex + 2) > '5') {// >255的25X
				return false;
			}
		}

		return true;
	}

}
